import java.util.Arrays;

public class Heap {

    public int[] elem;
    public int usedsize;

    public Heap(){
        this.elem = new int[10];
    }
    public void init(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedsize ++;
        }
    }
    public void GreatHeap(){
        for (int parent =( usedsize -1-1)/2; parent >= 0; parent--) {
            siftmaxHeap(parent,usedsize);
        }
    }

    public void siftmaxHeap(int parent,int usedsize){
        int child = 2*parent + 1;
        while(child < usedsize){
            if(child +1 < usedsize && elem[child+1] > elem[child]){
                child++;
            }
            //elem[child] 跟 elem[parent] 进行比较，交换。
            if(elem[child] > elem[parent]){
                swap(elem,parent,child);
                parent = child;
                child = 2*parent +1;
            }else {
                break;
            }

        }
    }
    public void swap(int[] elem,int parent,int child){
        int k = elem[parent];
        elem[parent] = elem[child];
        elem[child] = k;
    }
    public void offer(int val){
        if(elem.length == usedsize){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedsize] = val;
        usedsize++;
        siftup(usedsize);
    }
    public void siftup(int size){
        int parent = (size-1-1)/2;
        int child = size-1;
        while (parent >= 0){
            if (elem[child] > elem[parent]){
                swap(elem,parent,child);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    public void poll(int set){
        swap(elem,set,usedsize-1);
        usedsize--;
        siftmaxHeap(set,usedsize);
    }
    public int peek() {
        return elem[0];
    }
    public void smallestk(int[] count,int k){
        for (int i = 0; i < k; i++) {
            offer(count[i]);
        }

        for (int i = k; i < count.length; i++) {
            int cur = peek();
            if (cur > count[i]){
                poll(0);
                offer(count[i]);
            }

        }
        }
    public void printf(){
        for (int i = 0; i < elem.length; i++) {
            System.out.print(elem[i]);
        }
    }
}
